package com.zhugang.week05;

/**
 * @program algorithms
 * @description: peakIndexInMountainArray
 * @author: chanzhugang
 * @create: 2022/07/04 21:54
 */
public class peakIndexInMountainArray {

    public static void main(String[] args) {
        peakIndexInMountainArray peakIndexInMountainArray = new peakIndexInMountainArray();
        int[] arr = new int[]{6, 7, 8, 5, 4, 3};
        int index = peakIndexInMountainArray.peakIndexInMountainArray(arr);
        System.out.println(index);
    }

    /**
     * 852 山脉数组的峰值索引
     *
     * @param arr
     * @return
     */
    public int peakIndexInMountainArray(int[] arr) {
        // 画图：先增后减， 看成上坡和下坡
        int n = arr.length;
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid == 0) {
                // 特殊处理边界
                low = mid + 1;
            } else if (mid == n - 1) {
                // 处理边界
                high = mid - 1;
            } else if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                return mid;
            } else if (arr[mid] > arr[mid - 1]) {
                // 上坡
                low = mid + 1;
            } else {
                // 下坡
                high = mid - 1;
            }
        }
        return -1;
    }
}